"""
$Id: __init__.py 2 2007-03-04 19:08:44Z sidnei.da.silva $
"""

import time
import textwrap

class ConflictError(Exception): pass

class Operation(dict):

    t_map = {'read':'r',
             'write':'w',
             'commit':'c',
             'abort':'a',
             'lock_exclusive':'lx',
             'lock_shared':'ls',
             'unlock_exclusive':'ux',
             'unlock_shared':'us'}

    def __repr__(self):
        info = self['transaction']
        if self.has_key('data'):
            info = '%s[%s]' % (info, self['data'])
        return '%s%s' % (self.t_map.get(self['type']), info)

    def __getattr__(self, name):
        if not self.has_key(name):
            raise AttributeError, name
        return self[name]

    def execute(self, context, transaction):
        now = transaction.ts
        if not self.has_key('data'):
            return
        name = self['data']
        kw = {'name':name}
        kw['wts'] = self['type'] in ('write',) and now or None
        kw['rts'] = self['type'] in ('read',) and now or None
        if not context.data.has_key(name):
            context.data[name] = data = Data(**kw)
            # First operation does nothing
            return data

        data = context.data[name]

        # If a transaction T wants to read O, and TS(T) < WTS(O), the
        # order of the read with respect to the most recent write on O
        # would violate the timestamp order between transaction and
        # writer. So, T is aborted and restarted with a new, larger
        # timestamp.
        if (self['type'] in ('read',) and
            transaction.ts < data.wts):
            context.steps.append('case1')
            raise ConflictError, data

        # If a transaction T wants to read O, and TS(T) >
        # WTS(O), T reads O, RTS(O) is set to max[RTS(O), TS(T)].
        if (self['type'] in ('read',) and
            transaction.ts > data.wts):
            data.rts = max(data.rts, transaction.ts)
            context.steps.append('case2')
            return data

        # If a transaction T wants to write O, if TS(T) < RTS(O), the
        # write action would conflict with the read action of O and T
        # is aborted and restarted.
        if (self['type'] in ('write',) and
            transaction.ts < data.rts):
            context.steps.append('case3')
            raise ConflictError, data

        # If a transaction T wants to write O, if TS(T) < WTS(O), we
        # use the Thomas Write Rule and ignore this write to O and
        # continue.
        if (self['type'] in ('write',) and
            transaction.ts < data.wts):
            context.steps.append('case4')
            return data

        # Otherwise, T writes to O, and WTS(O) is set to TS(T).
        if (self['type'] in ('write',) and
            transaction.ts > data.wts):
            data.wts = transaction.ts
            context.steps.append('case5')
            return data

        context.steps.append(('unhandled', self, data,
                              transaction.ts, transaction))
        return data

class Data(dict):

    def __getattr__(self, name):
        if not self.has_key(name):
            raise AttributeError, name
        return self[name]

class Transaction(list):

    def __init__(self, id, *args, **kw):
        ts = kw.get('ts')
        if ts is None:
            ts = time.time()
        list.__init__(self, args)
        self.id = id
        self.ts = ts

    def __repr__(self):
        info = ', '.join([repr(o) for o in self])
        info = '\n'.join(textwrap.wrap(info, 50))
        return 't%s: %s' % (self.id, info)

    def __cmp__(self, other):
        me = (self.id, tuple(self))
        other = (other.id, tuple(other))
        return cmp(me, other)

    def reset(self):
        self.ts = time.time()

    def new(self):
        return Transaction(self.id, ts=None, *self)

    def copy(self, reverse=True):
        l = list(self)
        if reverse:
            l.reverse()
        return Transaction(self.id, ts=self.ts, *l)

class History(list):

    def __init__(self, id=None, *args, **kw):
        list.__init__(self, args)
        self.id = id
        self._transactions = {}
        transactions = kw.get('transactions', [])
        if transactions:
            self.update(*transactions)

    def __repr__(self):
        info = ', '.join([repr(o) for o in self])
        info = '\n'.join(textwrap.wrap(info, 50))
        return 'h%s: %s' % (self.id, info)

    def __cmp__(self, other):
        me = (self.id, tuple(self))
        other = (other.id, tuple(other))
        return cmp(me, other)

    def set_transactions(self, transactions):
        self._transactions = transactions

    def transactions(self):
        return self._transactions.itervalues()

    def get_transaction(self, tid):
        return self._transactions[tid]

    def update(self, *transactions, **kw):
        start = kw.get('start', 0)
        lts = len(transactions)
        for tn, t in enumerate(transactions):
            lt = len(t)
            for on, o in enumerate(t):
                # Use a deterministic algorithm to sort operations
                # from different transactions.
                ls = len(self)
                if t.id in self._transactions:
                    ts = len(self._transactions)
                    # Re-inserting aborted transaction
                    pos = start + ts * on
                else:
                    td = tn + 1
                    pos = td + td * on
                if pos > ls:
                    pos = ls
                self.insert(pos, o)
            self._transactions[t.id] = t
        if self.id is None:
            self.id = ''.join(self._transactions.keys())

    def copy(self, reverse=False):
        l = list(self)
        if reverse:
            l.reverse()
        history = History(self.id, *l)
        history._transactions = self._transactions.copy()
        return history

    def handle_conflict(self, operation, transaction, h_pos):
        # When a conflict occurrs, we abort the current
        # transaction at the point the conflict occurred
        # and build a new history retrying the transaction
        h_pos += 1
        abort = Operation(type='abort', transaction=transaction.id)
        self.insert(h_pos, abort)
        new_history = self.copy()
        t_pos = transaction.index(operation)
        for o in transaction[t_pos+1:]:
            new_history.remove(o)
        new_history.update(transaction.new(), start=h_pos+1)
        return new_history

class ExecutionContext(object):

    def __init__(self, history=None, transactions=None):
        if history is None:
            history = History(None)
        if transactions is not None:
            history.update(*transactions)
        self.original_history = history
        self.history = history.copy()
        self.data = {}
        self.steps = []

    def __iter__(self):
        return self.next()

    def next(self):
        pos = 0
        while True:
            if pos == len(self.history):
                break
            o = self.history[pos]
            t = self.history.get_transaction(o.transaction)
            try:
                yield o.execute(self, t)
            except ConflictError:
                self.history = self.history.handle_conflict(o, t, pos)
            pos += 1
        raise StopIteration
